package com.test.leetcode;

/**
 * https://leetcode.cn/problems/unique-paths/
 * @author sujiafa
 * @date 2025/1/24
 */
public class n62_不同路径 {

    public int uniquePaths(int m, int n) {

        int[][] grid = new int[m][n];
        // 第一行和第一列只可能有一种路径
        for (int i = 0; i < n; i++) {
            grid[0][i] = 1;
        }
        for (int j = 0; j < m; j++) {
            grid[j][0] = 1;
        }

        // 对应网格的路径数f(m,n) = f(m-1,n) + f(m,n-1)
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                grid[i][j] = grid[i - 1][j] + grid[i][j - 1];
            }
        }

        return grid[m-1][n-1];
    }

    /**
     * 空间复杂度O(n)
     */
    public int uniquePaths2(int m, int n) {

        // 初始化第一行
        int[] grid = new int[n];
        for (int i = 0; i < n; i++) {
            grid[i] = 1;
        }

        for (int j = 1; j < m; j++) {
            // 等同于f(m,n) = f(m-1,n) + f(m,n-1)
            for (int i = 1; i < n; i++) {
                grid[i] = grid[i] + grid[i - 1];
            }
        }

        return grid[n - 1];
    }
}
